package medium;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/6/26 17:47
 */
public class No93_复原IP地址 {
    public static void main(String[] args) {
        Solution93 solution93 = new Solution93();
        String s = "130203";
        List<String> list = solution93.restoreIpAddresses(s);
        System.out.println(list);
    }
}

class Solution93 {
    public List<String> restoreIpAddresses(String s) {
        //递归实现
        List<String> res = new ArrayList<>();
        restoreIpAddresses(s, 0, 0, "", res);
        return res;
    }

    // deep:递归深度,必须是4才行
    // start:递归起始位置
    // add:每层递归获取的符合题意的字符串部分
    public void restoreIpAddresses(String s, int deep, int start, String add, List<String> res) {
        //深度是4,每个1有一个"."
        if (deep == 4 && add.length() == s.length() + 4) {
            //递归深度已经是4,同时注意:已经递归的字符串全部拿完才行
            //加结果
            res.add(add.substring(0, add.length() - 1));
            return;
        }
        //每层深度最多3次  0,01,012
        for (int i = start; i <= start + 2; i++) {
            //注意越界问题
            if (i <= s.length() - 1) {
                // [)
                //每层获取的字符串
                String base = s.substring(start, i + 1);
                //前导0,255判断
                int baseInt = Integer.valueOf(base);
                if (baseInt > 255 || (baseInt + "").length() != base.length()) {
                    continue;
                }

                //符合
                add += base + ".";

                //下一轮
                restoreIpAddresses(s, deep + 1, i + 1, add, res);
                //回溯
                add = add.substring(0, add.length() - 1);
                add = add.substring(0, add.length() - base.length());
            }
        }
    }
        
}



    //public List<String> restoreIpAddresses(String s) {
    //    //暴力法
    //    //获取每个组的长度从1-3开始遍历
    //    List<String> res = new ArrayList<>();
    //    for (int a = 1; a <= 3; a++) {
    //        for (int b = 1; b <= 3; b++) {
    //            for (int c = 1; c <= 3; c++) {
    //                for (int d = 1; d <= 3; d++) {
    //                    if (a + b + c + d != s.length()) {
    //                        //说明没有全拿,跳过
    //                        continue;
    //                    }
    //                    
    //                    //通过每个组的长度获取字符串
    //                    //第一组
    //                    int indexOneA = 0;
    //                    int indexOneB = indexOneA + a;
    //                    
    //                    //第二组
    //                    int indexTwoA = indexOneB;
    //                    int indexTwoB = indexTwoA + b;
    //                    
    //                    //第三组
    //                    int indexThreeA = indexTwoB;
    //                    int indexThreeB = indexThreeA + c;
    //                    
    //                    //第四组
    //                    int indexFourA = indexThreeB;
    //                    int indexFourB = indexFourA + d;
    //                    
    //                    //开始切割
    //                    try {
    //                        String oneStr = s.substring(indexOneA, indexOneB);
    //                        String twoStr = s.substring(indexTwoA, indexTwoB);
    //                        String threeStr = s.substring(indexThreeA, indexThreeB);
    //                        String fourStr = s.substring(indexFourA, indexFourB);
    //                        
    //                        //有可能有前导0,也有可能有超过255
    //                        if (Integer.valueOf(oneStr) > 255 ||
    //                                Integer.valueOf(twoStr) > 255 ||
    //                                Integer.valueOf(threeStr) > 255 ||
    //                                Integer.valueOf(fourStr) > 255) {
    //                            throw new Exception("超出255bug!!!");
    //                        }
    //                        
    //                        //如果改成int的长度与组长度不同,则说明有前导0
    //                        if (((Integer.valueOf(oneStr) + "").length() != a) ||
    //                                ((Integer.valueOf(twoStr) + "").length() != b) ||
    //                                ((Integer.valueOf(threeStr) + "").length() != c) ||
    //                                ((Integer.valueOf(fourStr) + "").length() != d)) {
    //                            throw new Exception("前导0bug!");
    //                        }
    //                        
    //                        
    //                        //说明是有效值
    //                        // 10.255.13.17
    //                        StringBuffer stringBuffer = new StringBuffer();
    //                        stringBuffer.append(oneStr).append(".")
    //                                .append(twoStr).append(".")
    //                                .append(threeStr).append(".")
    //                                .append(fourStr);
    //                        res.add(stringBuffer.toString());
    //                        
    //                    } catch (Exception e) {
    //                        //啥都不做
    //                    }
    //                }
    //            }
    //        }
    //    }
    //    return res;
    //}


